#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// Kadane algorithm
// 所有相邻元素构成的子数组的最大和
// arr
//  3, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4
// sum
//[ 3, 8, -1, 1, 4,  2,                                 ] 

// sum[0] = arr[0]
// sum[i] = max(arr[i], sum[i - 1] + arr[i])

// 
// 新数组的每一个索引
// 以原数组对应位置为最后一个元素的子数组能产生的最大和
int kadane(const vector<int> &arr) {
  vector<int> result(arr.size(), 0);
  result[0] = arr[0];

  for (int i = 1; i < arr.size(); ++i) {
    result[1] = max(arr[i], arr[i] + result[i - 1]);
  }

  return *max_element(result.begin(), result.end());
}

int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}
